1. Field of the Invention
This invention relates to programmable digital data processors which process so-called vector instructions, particularly vector reduction instructions. More specifically, it relates to a novel method and apparatus for performing vector reductions.
2. Description of the Prior Art As will be appreciated by those skilled in the art, in certain data processing applications, particularly computational applications carried out in scientific processors, it is advantageous to have an efficient hardware implementation of an instruction called a "vector reduction" instruction. A vector can be thought of as simply a column of binary numbers or other specified data stored in predetermined locations in a memory or register. The reduction operation is, for example, addition or multiplication yielding a result which is the sum or product of all the elements of the vector. Reduction operations may include not only addition and multiplication, but also logical operations and comparisons for determining the largest or smallest element of the vector.
Instructions and techniques for implementing vector reductions are known in the prior art. Most prior art algorithms or strategies are straight forward. FIG. 1 illustrates graphically one prior art strategy. Here a vector comprised of data elements X.sub.O through X.sub.n are reduced to a single result (called a scalar) through addition. The data elements or operands are combined sequentially. That is, the partial result of X.sub.0 +X.sub.1 is first obtained and this partial result (X.sub.0 +X.sub.1 is combined with X.sub.3 ((X.sub.0 +X.sub.1)+X.sub.3) and that partial result is then combined with X.sub.4 and so on.
This prior art approach has several disadvantages. Digital data processors, as a practical matter, have a limit on the size of the number which they can handle on either side of the decimal point. With the prior art vector reduction techniques there is a possibility of temporary overflows and round-off error accumulation. The ordering or sequence of the entire vector can be important.
Objects of this invention include the provision of a novel, stable method and a low hardware cost implementation for performing vector reductions, particularly in scientific processors where there is an emphasis on a large number of floating point computations.